package problem234_Palindrome_Linked_List;

import problem19_RemoveNthNodeFromEndofList.Solution.ListNode;

/**
 *	将list 的后一半逆序，与前一半比对
 */
public class Solution {
	public boolean isPalindrome(ListNode head) {
		if(head==null||head.next==null)
			return true;
		ListNode slow=head,fast=head;
		while(fast.next!=null&&fast.next.next!=null){
			slow=slow.next;
			fast=fast.next.next;
		}
		//逆序
		ListNode p1=slow.next,p2=p1.next,secondHead=slow.next;
		slow.next=null;
		while(p2!=null){
			ListNode tmp=p2.next;
			p2.next=p1;
			p1=p2;
			p2=tmp;
		}
		secondHead.next=null;
		//比对
		ListNode p=head,q=p1;
		while(q!=null){
			if(p.val!=q.val)
				return false;
			p=p.next;
			q=q.next;
		}
		return true;
	}
}
